/*-------------------------------------------------------------------------
 *
 * fsmpage.c
 *	  搜索和操作一个 FSM 页的例程。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/storage/freespace/fsmpage.c
 *
 * NOTES:
 *
 *	本文件中的公共函数形成一个 API，将 FSM 页的内部结构隐藏。这允许 freespace.c 将每个 FSM 页视为具有 SlotsPerPage “插槽”的黑箱。fsm_set_avail() 和 fsm_get_avail() 让你获取/设置插槽的值，而 fsm_search_avail() 让你搜索值 >= X 的插槽。
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "storage/bufmgr.h"
#include "storage/fsm_internals.h"

/* 宏用于在页面内导航树。根节点的索引为零。 */
#define leftchild(x)	(2 * (x) + 1)
#define rightchild(x)	(2 * (x) + 2)
#define parentof(x)		(((x) - 1) / 2)

/* 
 * 查找x的右邻居，在层内环绕
 */
static int fc_rightneighbor(int fc_x)
{
	/* 
	 * 向右移动。这可能会环绕，步入下一个级别的最左节点。
	 */
	fc_x++;

	/* 
	 * 检查我们是否已步入下一个级别的最左节点，如果是，进行校正。
	 * 每个级别的最左节点编号为x = 2^level - 1，
	 * 因此检查(x + 1)是否是2的幂，使用标准的
	 * 补码算术技巧。
	 */
	if (((fc_x + 1) & fc_x) == 0)
		fc_x = parentof(fc_x);

	return fc_x;
}

/* 
 * 设置页面上一个槽的值。如果页面被修改，则返回true。
 *
 * 调用者必须对页面保持独占锁。
 */
bool fsm_set_avail(Page fc_page, int fc_slot, uint8 fc_value)
{
	int			fc_nodeno = NonLeafNodesPerPage + fc_slot;
	FSMPage		fc_fsmpage = (FSMPage) PageGetContents(fc_page);
	uint8		fc_oldvalue;

	Assert(fc_slot < LeafNodesPerPage);

	fc_oldvalue = fc_fsmpage->fp_nodes[fc_nodeno];

	/* 如果值没有改变，我们不需要做任何事情 */
	if (fc_oldvalue == fc_value && fc_value <= fc_fsmpage->fp_nodes[0])
		return false;

	fc_fsmpage->fp_nodes[fc_nodeno] = fc_value;

	/* 
	 * 向上传播，直到我们到达根或不需要
	 * 更新的节点。
	 */
	do
	{
		uint8		fc_newvalue = 0;
		int			fc_lchild;
		int			fc_rchild;

		fc_nodeno = parentof(fc_nodeno);
		fc_lchild = leftchild(fc_nodeno);
		fc_rchild = fc_lchild + 1;

		fc_newvalue = fc_fsmpage->fp_nodes[fc_lchild];
		if (fc_rchild < NodesPerPage)
			fc_newvalue = Max(fc_newvalue,
						   fc_fsmpage->fp_nodes[fc_rchild]);

		fc_oldvalue = fc_fsmpage->fp_nodes[fc_nodeno];
		if (fc_oldvalue == fc_newvalue)
			break;

		fc_fsmpage->fp_nodes[fc_nodeno] = fc_newvalue;
	} while (fc_nodeno > 0);

	/* 
	 * 健全性检查：如果新值（仍然）高于顶部的值，
	 * 树是损坏的。如果是这样，请重建。
	 */
	if (fc_value > fc_fsmpage->fp_nodes[0])
		fsm_rebuild_page(fc_page);

	return true;
}

/* 
 * 返回页面上给定槽的值。
 *
 * 由于这只是对单个字节的只读访问，因此页面不
 * 需要被锁定。
 */
uint8 fsm_get_avail(Page fc_page, int fc_slot)
{
	FSMPage		fc_fsmpage = (FSMPage) PageGetContents(fc_page);

	Assert(fc_slot < LeafNodesPerPage);

	return fc_fsmpage->fp_nodes[NonLeafNodesPerPage + fc_slot];
}

/* 
 * 返回页面根部的值。
 *
 * 由于这只是对单个字节的只读访问，因此页面不
 * 需要被锁定。
 */
uint8 fsm_get_max_avail(Page fc_page)
{
	FSMPage		fc_fsmpage = (FSMPage) PageGetContents(fc_page);

	return fc_fsmpage->fp_nodes[0];
}

/* 
 * 搜索类别至少为minvalue的槽。
 * 返回槽号，如果未找到则返回-1。
 *
 * 调用者必须至少对页面保持共享锁，如果需要
 * 更新，此函数可以解锁并再次锁定页面为独占模式。
 * 如果调用者已经持有独占锁，则应将exclusive_lock_held设置为true，以避免额外的工作。
 *
 * 如果advancenext为false，则fp_next_slot被设置为指向返回的
 * 槽，如果为true，则指向返回槽之后的槽。
 */
int fsm_search_avail(Buffer fc_buf, uint8 fc_minvalue, bool fc_advancenext,
				 bool fc_exclusive_lock_held)
{
	Page		fc_page = BufferGetPage(fc_buf);
	FSMPage		fc_fsmpage = (FSMPage) PageGetContents(fc_page);
	int			fc_nodeno;
	int			fc_target;
	uint16		fc_slot;

restart:

	/* 
	 * 首先检查根，如果没有足够的自由空间的叶子，则快速退出
	 */
	if (fc_fsmpage->fp_nodes[0] < fc_minvalue)
		return -1;

	/*
	 * 使用 fp_next_slot 开始搜索。这只是一个提示，所以检查它是否
	 * 合理。 （这也处理在先前调用返回页面的最后插槽时的循环情况。）
	 */
	fc_target = fc_fsmpage->fp_next_slot;
	if (fc_target < 0 || fc_target >= LeafNodesPerPage)
		fc_target = 0;
	fc_target += NonLeafNodesPerPage;

	/*----------
	 * 从目标插槽开始搜索。在每一步中，向右移动一个节点，
	 * 然后爬上父节点。当我们到达有足够空闲空间的节点时停止
	 * （因为我们必须这样做，因为根节点有足够的空间）。
	 *
	 * 这个想法是逐渐扩展我们的“搜索三角形”，即由当前节点覆盖的所有
	 * 节点，并确保我们从起始点向右搜索。在第一步中，只检查目标插槽。
	 * 当我们从左子节点向上移动到其父节点时，我们向搜索三角形
	 * 添加该父节点的右侧子树。当我们从右子节点向右再向上移动时，
	 * 我们放弃当前的搜索三角形（我们知道不包含任何合适的
	 * 页面），而是查看其右侧的下一个较大尺寸的三角形。
	 * 因此，我们永远不会从原始起点向左查看，并且在每一步中，
	 * 搜索三角形的大小翻倍，确保搜索 N 页仅需 log2(N) 的工作量。
	 *
	 * “向右移动”操作会在遇到树的右边缘时环绕，因此如果我们
	 * 从右边开始，行为仍然良好。注意，移动和攀登的行为确保
	 * 我们无法止步于叶级右侧的缺失节点之一。
	 *
	 * 例如，考虑这个树：
	 *
	 *		   7
	 *	   7	   6
	 *	 5	 7	 6	 5
	 *	4 5 5 7 2 6 5 2
	 *				T
	 *
	 * 假设目标节点是字母 T 所指示的节点，并且我们在寻找值为
	 * 6 或更高的节点。搜索从 T 开始。在第一次迭代中，我们向右移动，
	 * 然后向上到达最右侧的 5。在第二次迭代中，我们向右移动，
	 * 并进行环绕，然后爬上，达到第三层的 7。7 满足我们的搜索，
	 * 所以我们向下跟随 7 的路径到底部。这实际上是我们起始点
	 * 右侧第一个合适的页面（考虑环绕）。
	 *----------
	 */
	fc_nodeno = fc_target;
	while (fc_nodeno > 0)
	{
		if (fc_fsmpage->fp_nodes[fc_nodeno] >= fc_minvalue)
			break;

		/*
		 * 向右移动，如果有必要在同一层级上环绕，然后
		 * 向上爬升。
		 */
		fc_nodeno = parentof(fc_rightneighbor(fc_nodeno));
	}

	/*
	 * 我们现在处于一个有足够自由空间的节点，位于树的中间。下降到底部，沿着一条有足够自由空间的路径，优先选择向左移动。
	 */
	while (fc_nodeno < NonLeafNodesPerPage)
	{
		int			fc_childnodeno = leftchild(fc_nodeno);

		if (fc_childnodeno < NodesPerPage &&
			fc_fsmpage->fp_nodes[fc_childnodeno] >= fc_minvalue)
		{
			fc_nodeno = fc_childnodeno;
			continue;
		}
		fc_childnodeno++;			/* 指向右子节点 */
		if (fc_childnodeno < NodesPerPage &&
			fc_fsmpage->fp_nodes[fc_childnodeno] >= fc_minvalue)
		{
			fc_nodeno = fc_childnodeno;
		}
		else
		{
			/*
			 * 哦，父节点承诺左或右子节点有足够空间，但其实都没有。这可能发生在“撕裂的页面”情况下，也就是说如果我们在写页面到磁盘时崩溃，只有部分页面成功写入磁盘。
			 *
			 * 修复损坏并重启。
			 */
			RelFileNode fc_rnode;
			ForkNumber	fc_forknum;
			BlockNumber fc_blknum;

			BufferGetTag(fc_buf, &fc_rnode, &fc_forknum, &fc_blknum);
			elog(DEBUG1, "fixing corrupt FSM block %u, relation %u/%u/%u",
				 fc_blknum, fc_rnode.spcNode, fc_rnode.dbNode, fc_rnode.relNode);

			/* 确保我们持有独占锁 */
			if (!fc_exclusive_lock_held)
			{
				LockBuffer(fc_buf, BUFFER_LOCK_UNLOCK);
				LockBuffer(fc_buf, BUFFER_LOCK_EXCLUSIVE);
				fc_exclusive_lock_held = true;
			}
			fsm_rebuild_page(fc_page);
			MarkBufferDirtyHint(fc_buf, false);
			goto restart;
		}
	}

	/* 我们现在在最底层，处于一个有足够空间的节点。 */
	fc_slot = fc_nodeno - NonLeafNodesPerPage;

	/*
	 * 更新下一个目标指针。请注意，即使我们只持有共享锁，我们也这样做，理由是使用共享锁并偶尔得到一个混乱的下一个指针，总比承担独占锁的并发代价要好。
	 *
	 * 环绕在此函数的开头处理。
	 */
	fc_fsmpage->fp_next_slot = fc_slot + (fc_advancenext ? 1 : 0);

	return fc_slot;
}

/*
 * 将所有编号 >= nslots 的插槽的可用空间设置为零。
 * 如果页面被修改则返回true。
 */
bool fsm_truncate_avail(Page fc_page, int fc_nslots)
{
	FSMPage		fc_fsmpage = (FSMPage) PageGetContents(fc_page);
	uint8	   *fc_ptr;
	bool		fc_changed = false;

	Assert(fc_nslots >= 0 && fc_nslots < LeafNodesPerPage);

	/* 清除所有被截断的叶子节点 */
	fc_ptr = &fc_fsmpage->fp_nodes[NonLeafNodesPerPage + fc_nslots];
	for (; fc_ptr < &fc_fsmpage->fp_nodes[NodesPerPage]; fc_ptr++)
	{
		if (*fc_ptr != 0)
			fc_changed = true;
		*fc_ptr = 0;
	}

	/* 修复上层节点。 */
	if (fc_changed)
		fsm_rebuild_page(fc_page);

	return fc_changed;
}

/*
 * 重建页面的上层。如果页面被修改，则返回true。
 */
bool fsm_rebuild_page(Page fc_page)
{
	FSMPage		fc_fsmpage = (FSMPage) PageGetContents(fc_page);
	bool		fc_changed = false;
	int			fc_nodeno;

	/*
	 * 从最低的非叶层开始，从最后一个节点向后工作，
	 * 通过所有层级的非叶节点，一直到根节点。
	 */
	for (fc_nodeno = NonLeafNodesPerPage - 1; fc_nodeno >= 0; fc_nodeno--)
	{
		int			fc_lchild = leftchild(fc_nodeno);
		int			fc_rchild = fc_lchild + 1;
		uint8		fc_newvalue = 0;

		/* 我们检查的前几个节点可能有零个或一个子节点。 */
		if (fc_lchild < NodesPerPage)
			fc_newvalue = fc_fsmpage->fp_nodes[fc_lchild];

		if (fc_rchild < NodesPerPage)
			fc_newvalue = Max(fc_newvalue,
						   fc_fsmpage->fp_nodes[fc_rchild]);

		if (fc_fsmpage->fp_nodes[fc_nodeno] != fc_newvalue)
		{
			fc_fsmpage->fp_nodes[fc_nodeno] = fc_newvalue;
			fc_changed = true;
		}
	}

	return fc_changed;
}
